package graph.base.minpath;

import graph.GraphNode;
import graph.graphtype.NoDirectWeightGraph;
import java.util.Stack;

/**
 * 最短路算法：迪杰斯特拉算法（单源点多路径）
 * 原理：
 *  1、定义分量X[n,f,d,p]
 *  n表示一个节点
 *  f表示是否访问过
 *  d表示源点到该节点的最小距离
 *  p源点到该点最小距离经过的前一个节点
 *
 *  2、定义数组X[size]，将源点分量置为[n,1,0,-1]
 *  3、已访问的节点组成集合U，在U中寻找一条指向集合外最短的边，并将该点的分量置为[n,1,d(p-1) + w,p-1]
 *      w表示选取的最小边的权重
 *      p-1表示U集合中的点
 *      d(p-1)表示U集合中点的d值
 *
 *      p-1这个点可能不是当前这条选出来的路径，可能会是U中的其他点。
 *      这里的含义是：需要比较通过一个中转点 或者 直接到达 的权重，如果当前选出的路径确实是最终最小的则表示通过中转点有更小的权重
 *      可以直连的点是U中的所有点
 *
 *  4、重复3操作，直到所有点都加入集合U中
 *
 *  5、d分量表示源点到该点的最小权重
 *  6、最终的路径可根据p分量回溯出来
 */

public class Dijkstra {

    NoDirectWeightGraph g;
    int[][] stat;
    int[] visited;

    public Dijkstra(NoDirectWeightGraph g) {
        this.g = g;
        stat = new int[g.table.length][4];

        for (int i = 0; i < g.table.length; i++) {

            stat[i][0] = i;
            stat[i][1] = 0;
            stat[i][2] = 0;
            stat[i][3] = -1;

        }

        visited = new int[g.table.length];
    }

    public void dijkstra(int nodeSrc, int nodeDst) {
        stat[nodeSrc][1] = 1;
        visited[nodeSrc] = 1;

        int count = 0;
        while (count++ < visited.length) {
            int[] minEdge = new int[]{0, 0, Integer.MAX_VALUE};// src, dst, weight
            for (int i = 0; i < visited.length; i++) {
                if (visited[i] == 1) {
                    int[] tempMinEdge = g.table[i].getMinNode(visited);
                    if (tempMinEdge[2] < minEdge[2]) {
                        minEdge[0] = tempMinEdge[0];
                        minEdge[1] = tempMinEdge[1];
                        minEdge[2] = tempMinEdge[2];
                    }
                }
            }
            int[] directWeight = directMinWeight(visited, minEdge[1], stat);

            visited[minEdge[1]] = 1;
            // 查看直连是否有更小的路径
            if (directWeight[2] < minEdge[2] + stat[minEdge[0]][2]){
                stat[minEdge[1]][1] = 1;
                stat[minEdge[1]][2] = stat[directWeight[1]][2] + directWeight[2];
                stat[minEdge[1]][3] = directWeight[1];// pre node
            }else {
                stat[minEdge[1]][1] = 1;
                stat[minEdge[1]][2] = stat[minEdge[0]][2] + minEdge[2];
                stat[minEdge[1]][3] = minEdge[0];// pre node
            }

        }
        System.out.println("================");

        Stack<Integer> r = new Stack<>();
        int node = nodeDst;
        while(node != nodeSrc){
            r.push(node);
            node = stat[node][3];
        }

        r.push(nodeSrc);
        System.out.println(nodeSrc + " to " + nodeDst + ", min: " + stat[nodeDst][2]);
        while (!r.isEmpty()){
            Integer n = r.pop();
            if (!r.isEmpty()){
                System.out.print(n + "->");
            }else{
                System.out.print(n);
            }
        }

    }

    private int[] directMinWeight(int[] visited, int node, int[][] stat) {
        int[] min = new int[]{0, 0, Integer.MAX_VALUE};
        GraphNode tempNext = g.table[node].next;

        while (tempNext != null){
            if (visited[tempNext.id] == 1){
                int[] w = tempNext.edgeNode.getWeight(node);
                if (w[1] + stat[tempNext.id][2] < min[2]){
                    min[0] = w[0];
                    min[1] = tempNext.id;
                    min[2] = w[1];
                }
            }
            tempNext = tempNext.next;
        }

        return min;
    }

    public static void main(String[] args) {
        int[][] edges = new int[][]{{0, 1, 3}, {0, 2, 5}, {0, 4, 1},
                {1, 0, 3}, {1, 3, 1}, {2, 0, 5}, {2, 3, 2}, {2, 4, 4}, {3, 1, 1},
                {3, 2, 2}, {3, 4, 3}, {4, 0, 1}, {4, 2, 4}, {4, 3, 3}};
        int[] data = new int[]{1, 2, 3, 4, 5};
        NoDirectWeightGraph g = new NoDirectWeightGraph(data.length, data);
        g.generateGraph(edges);

        new Dijkstra(g).dijkstra(0, 3);

    }

}
